%!TEX root = paper.tex

\section{Related Works and Discussion}
\label{sec:discuss}

Visualization-assisted data analysis has recently attracted a lot
of attention in both database and CHI communities.
Jugel et~al.~\cite{vldb14-JugelJerzakEtAl-m4} studied data reduction
techniques for high-volume time series data driven by visualization
constraints, while our work is motivated by limit on data access.
Along the same line, the idea of data reduction for efficient
visualization of time series data had previously been explored by
Burtini et~al.~\cite{ccece13-BurtiniFazackerleyLawrence-time_series_compress}.

The problem of rapid generation of approximate visualizations while
preserving crucial properties was studied by Blais
et~al.~\cite{arxiv2014-KimBlaisEtAl-sample_vis} for bar chart, which
employs very different techniques.  Efficiency-precision tradeoff for
exploratory visualization of large dataset has also been studied in
the CHI
community~\cite{ldav11-Fisher-explore_vis,chi12-FisherPopovEtAl-inc_vis}.
% To the best of
% our knowledge, all existing work on data/computation reduction for
% rapid visualization relies heavily on knowing the transformation
% from input data to data for visualization, while we only assume
% the signature (input of output format) of this transformation.
The idea of using prefetching techniques to improve visualization
efficiency for real-time responses in an interactive environment has
been studied by Doshi et~al.~\cite{dasfaa03-DoshiRundensteinerWard-prefetch_vis}.
Kandel et~al.~presented \emph{Profiler} \cite{avi12-KandelParikhEtAl-profiler}
for visualization-assisted data exploration and anomaly detection
from an HCI perspective.

In this paper, we have considered outliers as points having a small
number of neighbors (thus not necessarily on the skyline), but the
idea of finding global outliers from promising objects by evaluating
sample data can apply to outliers of other forms, such as skyline
points~\cite{icde01-BorzsonyiKossmanStocker-skyline}.  The sketching
algorithm using points of $\Result^+ \setminus \RePreProx$ along with
$\Result^-$ with estimated counts can work as is.

The type of uniqueness-based fact-finding has been studied for skyline
and skyband points~\cite{sigkdd12-WuAgarwalEtAl-one_of_the_few}.
There, specialized algorithms were proposed to efficiently find all
interesting and unique points of a large point set; in this paper, we
propose a neighborhood sparsity based uniqueness definition and
propose an algorithm tailoring towards the visualization method
instead of the claim type.

The idea behind the two-phase sampling-based algorithm is related to
the notion of
\emph{coreset}~\cite{ccg05-AgarwalHarPeledVaradarajan-coreset_survey}
in computational geometry.  Since we do not have direct access to the
result set $\Result$, for each query instance $f$, we construct
``coresets'' of objects $\Obj^+$ and $\Obj^-$ instead of coresets of
points.  The selection of $\Obj^-$ using random sampling is analogous
to drawing random samples from the point
set~\cite{tpa71-VapnikChervonenkis-rel_freq,arxiv12-Phillips-chernoff}.
On the other hand, the selection of $\Obj^+$ is optimized towards
preserving another extent measure: minimum density points of
$\Result$.

Experiments in this paper are all conducted in memory.  However, at
service time, to support exploration query evaluation for many
datasets, and to avoid dedicating the memory to a single dataset,
objects' full data is hosted in
SSTable~\cite{tocs08-ChangDeanEtAl-bigtable} and brought into memory
only upon request via the SSTable service API.  Data accessing cost
will become even more dominant in the execution time.  In that case,
our sampling-based algorithm with a data access budget would increase
its advantage over the baseline algorithm.  Also, we have not explored
the possibility of parallel evaluation of query function $f$.  On
large data sets, parallel query evaluation for different objects will
further speed up the overall efficiency.

% Specialized sampling strategies may improve performance on certain
% query types

